# -*- coding: utf-8 -*-

"""剑指 Offer II 026. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

提示：
链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """题目要求：取首-取尾-取首-取尾-...
    思路转换：链表从中截断，后半段链表翻转，然后两个链表分别挨个取出组合成新链表"""
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        p, length = head, 0
        while p:
            length += 1
            p = p.next
        
        p, half = head, length//2
        if half == 0:
            half = 1
        while half-1:
            p = p.next
            half -=1
        
        second = p.next
        p.next = None

        if second:
            reverseed, follow = None, second.next
            while second:
                second.next = reverseed
                reverseed = second
                second = follow
                if follow:
                    follow = follow.next
            second = reverseed

        new = ListNode()
        tail = new
        while head:
            tail.next = head
            tail = tail.next
            head = head.next

            if second:
                tail.next = second
                tail = tail.next
                second = second.next
        
        head = new.next


def show_list_node(head):
    while head:
        print(head.val, end=', ')
        head = head.next
    print('')



if __name__ == '__main__':
    so = Solution()
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
    show_list_node(head)
    so.reorderList(head)
    show_list_node(head)

    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    show_list_node(head)
    so.reorderList(head)
    show_list_node(head)
